package StackOrQueue;

import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 *
 * 让数组的前半部分为大顶堆，需要最大值。后半部分为小顶堆，需要最小值
 * 偶数是两边数目一样，取大顶堆的最大值和小顶堆的最小值的平均
 * 奇数时，使左边数目多一个，直接取大顶堆的最大值即可
 * 由于左边的所有值都小于右边的。所以想往左边插入，则需先插入到右边的小顶堆，之后再弹出个最小的加到左边。反之亦然
 *
 * */

class TwoHeap {
    static PriorityQueue<Integer> min_heap=new PriorityQueue<>();  //小顶堆
    static PriorityQueue<Integer> max_heap=new PriorityQueue<>(((o1, o2) -> o2-o1)); //大顶堆

    static int count=0;//记录已获取数字的个数

    public static void Insert(Integer num) {
        //左边是大顶堆，保存数组小的前半部分，右边是小顶堆，保存数组大的后半部分
        //这样整体是有序的
        //由于左边的所有值都小于右边的。所以想往左边插入，则需先插入到右边的小顶堆，之后再弹出个最小的加到左边。反之亦然
        if(count%2==0){
            max_heap.offer(num);
            int tmp=max_heap.poll();
            min_heap.offer(tmp);
        }
        else{
            min_heap.offer(num);
            int tmp=min_heap.poll();
            max_heap.offer(tmp);
        }
        count++;
    }

    public static Double GetMedian() {
        if(count%2==0){
            return (double) (min_heap.peek() + max_heap.peek()) /2;
        }
        else{
            return new Double(min_heap.peek());
        }
    }

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(5, 2, 3, 4, 1, 6, 7, 0, 8);
        int index = 0;
        for (int i:list){
            TwoHeap.Insert(i);
            System.out.println((index++)+":"+TwoHeap.GetMedian());
        }
    }
}

